package com.hqq.leetcode.dp;

/**
 * BackPackVI 背包问题4
 * Description:
 * <p>
 * Given an integer array nums with all positive numbers and no duplicates,
 * find the number of possible combinations that add up to a positive integer target.
 * Input:
 * [1,2,4],4
 * Output:
 * 6
 * Created by heqianqian on 2017/9/17.
 */
public class BackPackVI {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 4};
        BackPackVI bp4 = new BackPackVI();
        int max = bp4.backPackVI(nums, 4);
        System.out.println(max);
    }

    /*
     * @param nums: an integer array and all positive numbers, no duplicates
        * @param target: An integer
        * @return: An integer
        */
    public int backPackVI(int[] nums, int target) {
        // write your code here
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int j = 1; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (j >= nums[i]) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}
